from .base import Sort


class Heap(Sort):
    '''堆排序'''

    def __init__(self, lt=True):
        super().__init__(lt)
        self.pq = [0]*(1)

    def name(self):
        return "堆排序"
    def sort(self, data, low=0, hight=None):
        hight = len(data) if hight is None else hight
        for i in range(low, hight):
            self.enqueue(data[i])

    def enqueue(self, item):
        '''将item添加道队列'''
        self.pq[0] += 1
        position = self.pq[0]
        if position < len(self.pq):
            self.pq[position] = item
        else:
            self.pq.append(item)
        self.swim(position)

    def dequeue(self):
        '''根节点出列，并做sink操作'''
        if self.pq[0] == 0:
            return None
        target = self.pq[1]
        if self.pq[0] > 1:
            self.exchange(self.pq, 1, self.pq[0])
            self.pq[0] -= 1
            self.sink(1)
        else:
            self.pq[0] -= 1
        return target

    def swim(self, position):
        '''节点做上浮处理'''
        if self.is_root(position):
            return
        parent = self.parent(position)
        if self.compare(self.pq[position], self.pq[parent]):
            self.exchange(self.pq, position, parent)
            self.swim(parent)

    def sink(self, position):
        '''节点做下沉处理'''
        if self.is_leaf(position):
            return
        left = self.left(position)
        right = self.right(position)
        if self.has_left(position):
            target = left
            if self.has_right(position):
                if self.compare(self.pq[right], self.pq[left]):
                    target = right
        else:
            target = right
        if self.compare(self.pq[target], self.pq[position]):
            self.exchange(self.pq, target, position)
            self.sink(target)

    def parent(self, position):
        return position // 2

    def left(self, position):
        return position * 2

    def right(self, position):
        return position * 2 + 1

    def is_root(self, position):
        return position == 1

    def is_leaf(self, position):
        return position * 2 > self.pq[0]

    def has_left(self, position):
        return position * 2 <= self.pq[0]

    def has_right(self, position):
        return position * 2 + 1 <= self.pq[0]
